; SICP, 2.61
; Give an implementation of adjoin-set using the ordered representation. By
; analogy with element-of-set? show how to take advantage of the ordering to
; produce a procedure that requires on the average about half as many steps
; as with the unordered representation.
;
; SICP, 2.62
; Give a θ(n) implementation of union-set for sets represented as ordered lists.

(define nil '())

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((= (car set) x) #t)
        ((> (car set) x) #f)
        (else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((= x (car set)) set)
        ((< x (car set)) (cons x set))
        (else
          (cons (car set)
                (adjoin-set x (cdr set))))))

(display (adjoin-set 5 '(2 3 6)))

(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
    nil
    (let ((i (car set1)) (j (car set2)))
      (cond ((= i j)
             (cons i
                   (intersection-set (cdr set1)
                                     (cdr set2))))
            ((< i j)
             (intersection-set (cdr set1) set2))
            ((> i j)
             (intersection-set set1 (cdr set2)))))))

(display (intersection-set '(1 3 5) '(1 2 3 4)))

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else
          (let ((i (car set1)) (j (car set2)))
            (cond ((= i j)
                   (cons i
                         (union-set (cdr set1) (cdr set2))))
                  ((< i j)
                   (cons i
                         (union-set (cdr set1) set2)))
                  ((> i j)
                   (cons j
                         (union-set set1 (cdr set2)))))))))

;(display (union-set '(2 3 4 5) '(1 2 3 4))) ; 1 2 3 4 5
